The present invention relates to a decoding apparatus, a decoding method and a program. More specifically, the present invention relates to a decoding apparatus, a decoding method, and a program capable of enhancing decoding performance in an error correction coding technology using an algebraic technique.
In the past, as a decoding method for algebraic-geometry codes such as Reed-Solomon codes or BCH (Bose-Chaudhuri-Hocquenghem) codes serving as sub-field partial codes, a method using the algebraic property of the codes and offering a good performance cost as well as a good computation cost is known.
Let us assume for example that notation n denotes a code length, notation k denotes an information length, notation GF (q) denotes a definition body where q=pm and p is a prime number and notation RS(n, k) denotes the Reed-Solomon code with a shortest distance d (n−k). In this case, a limit distance decoding method for decoding a received hard-decision word into a coded word having a shortest Hamming distance is commonly known as a method assuring correction of t erroneous symbols where notation t is a number satisfying a relation of t<d/2. In addition, a list decoding method introduced by Guruswami and Sudan assures correction of t erroneous symbols where notation t is a number satisfying a relation of T<√{square root over ( )}nk as described in a document such as non-patent document 1. The following reference is used as non-patent document 1: V. Guruswami, M. Sudan, Improved decoding of Reed-Solomon and Algebraic-Geometry codes, IEEE Transactions on Information Theory, vol. 45, pp 1757-1767, 1999. In the following description, the list decoding method introduced by Guruswami and Sudan is referred to simply as a G-S list decoding method.
As an extended version of the G-S list decoding method, much like the G-S list decoding method, a list decoding method introduced by Koetter and Vardy as a list decoding technique applied to a received soft-decision word includes four procedures, i.e., computation of reliability of each symbol from the received information, derivation of a condition for interpolation of two variable polynomials, interpolation of the two variable polynomials and creation of a decoded-word list obtained by factorization of a polynomial obtained as a result of the interpolation. In comparison with the method introduced for received hard decision words, the list decoding method introduced by Koetter and Vardy is known to have high performance as described in non-patent document 2. The following reference is used as non-patent document 2: R. Koetter, A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 2001. In the following description, the list decoding method introduced by Koetter and Vardy is referred to simply as a K-V list decoding method. In addition, there is also known a method for reducing the computation cost to a value in a practical range by carrying out a re-encoding process as described in non-patent document 3. The following reference is used as non-patent document 3: R. Koetter, J. Ma, A. Vardy, A. Ahmed, Efficient Interpolation and Factorization in Algebraic Soft-Decision decoding of Reed-Solomon codes, Proceedings of ISIT2003.
By the way, as a linear code, at the present time, an LDPC (Low Density Parity-check Code) draws attention as a code, which offers high performance close to limit performance by carrying out repetitive decoding processing adopting a belief propagation technique as described in non-patent document 4. The following reference is used as non-patent document 4: D. MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, 1999.
It is known theoretically that, in general, the belief propagation technique adopted for decoding a LDPC code is effective only for a linear code that has a low-density parity-check matrix. In addition, transformation of the parity-check matrixes of the Reed-Solomon codes and the BCH codes into low-density parity-check matrixes raises an NP-hard problem as explained in non-patent document 5. The following reference is used as non-patent document 5: Berlekamp, R. McEliece, H. van Tilborg, on the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, vol. 24, pp 384-386, 1978.
As is obvious from the above description, it is difficult to apply a decoding method adopting the belief propagation technique to the Reed-Solomon codes and the BCH codes.
In the year of 2004, however, by using a parity-check matrix completing a diagonalization operation in accordance with reliability of a received word, Narayanan et al. were capable of effectively applying a decoding method adopting the belief propagation technique to the Reed-Solomon codes, the BCH codes and linear codes having a parity-check matrix other than the low-density parity check matrix as disclosed in non-patent document 6. The following reference is used as non-patent document 6: Jing Jiang, K. R. Narayaman, Soft Decision Decoding of RS Codes Using Adaptive Parity Check Matrices. Proceedings of IEEE International Symposium on Information theory, 2004. The effectively applicable decoding method adopting the belief propagation technique is referred to as an ABP (Adaptive Belief Propagation) decoding method, which is described as follows.
Let us assume for example a linear code C having a parity check matrix H including 3 rows and 6 columns as shown in Eq. (1) given below, a code length n of 6, an information length k of 3, and an encoding rate of 1/2.
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                                                    0                                            1                                            1                                            1                                            1                                            1                                              )                                    (        1        )            
In this case, a code space C is expressed by Eq. (2) as follows.C={c=(c1,c2, . . . ,c6),c1,c2, . . . ,c6∈0,1|H·ct=0}  (2)
Let us assume that, after passing through a channel such as an AWGN (Adaptive White Gaussian Noise) channel following a BPSK (Binary Phase Shift Keying) process, a coded word is received by a receiver as a received word shown by Eq. (3) given as follows.r=(r1,r2, . . . ,r6)=(0.4,1,2,0.1,0.7.0.3,0.7)  (3)
In such a case, a decoding apparatus employed in the receiver carries out decoding processing with a flow thereof represented by a flowchart, which is explained by referring to FIG. 1 as follows.
The flowchart begins with a step S1 at which the decoding apparatus recognizes the reliability order of the received word. To put it concretely, the decoding apparatus regards the magnitude of the absolute value of each received symbol on the right side of Eq. (3) representing the equation of the received word as the level of the reliability of the symbol and, then, sets an order of the magnitudes of the absolute values as the order of reliability levels of the received symbols in the received word. That is to say, the decoding apparatus assigns order numbers each enclosed in a circle to received symbols in an increasing order with the smallest order number associated with the smallest magnitude of the absolute values of the received symbols as shown in Eq. (4) to result in an increasing order of reliability levels. As will be described later, in accordance with one of predetermined algorithms, the increasing order of reliability levels is adopted as an order of priority levels.
                              r          =                                    (                        ⁢                          0.4                                                    ,                  1.2                          ,                  0.1                          ,                  0.7                          ,                  0.3                          ,                              0.7                                ⁢                      )                                              (        4        )            
Then, at the next step S2, in accordance with a predetermined rule, the decoding apparatus rearranges the received symbols each having an order number assigned thereto in order to transform the existing priority order of the symbols into a new priority order for the next outer iteration loop from the step S2 to a step S9. For example, the existing priority order of the symbols is transformed into a new priority order, which is the increasing reliability order described above. As will be described later, as many rules different from each other as outer-side repetitions executed in repetitive decoding processing are prepared in advance and, each time one of the outer-side repetitions is executed, a different method according to a selected one of the prepared rules is adopted.
Then, at the next step S3 after the step of transforming the priority order into a new order, the decoding apparatus carries out a diagonalization operation on the parity-check matrix H in an execution order according to the new priority order. Let us assume for example that the priority order is transformed into a new priority order, which is the increasing reliability order described above. Thus, the new priority order starts with a symbol having the lowest level of reliability to be followed by symbols having gradually increasing levels of reliability. In this case, the decoding apparatus carries out a diagonalization operation on the parity-check matrix H in an execution order starting from a column corresponding to the symbol having the lowest level of reliability to be followed by columns corresponding to symbols having gradually increasing levels of reliability.
Since the new priority order starts with a symbol having the lowest level of reliability, in the typical case of the priority order shown in Eq. (4) as an order of increasing levels of reliability, a column included in the parity-check matrix H as a column corresponding to a symbol having the lowest level of reliability is column 3. A column corresponding to a symbol having a reliability level higher than the reliability level of column 3 is column 5. Columns each corresponding to a symbol having a reliability level higher than the reliability level of column 5 are columns 4 and 6. Finally, a column corresponding to a symbol having the highest level of reliability is column 2. Thus, the decoding apparatus carries out a diagonalization operation on the parity-check matrix H in accordance with these levels of priority.
That is to say, first of all, the decoding apparatus carries out a basic deformation operation on the parity-check matrix H with column 3 taken as the important one. To put it concretely, the decoding apparatus transforms the parity check matrix H into a matrix expressed by Eq. (5) by taking an exclusive logical sum of columns 1 and 3 and using the sum as a substitute for column 3 to give column 3 of ‘100’ as follows:
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                                                    1                                            1                                            0                                            1                                            1                                            0                                              )                                    (        5        )            
Then, the decoding apparatus carries out a basic deformation operation on the parity-check matrix H with column 5 taken as the important one. To put it concretely, the decoding apparatus transforms the parity check matrix H into a matrix expressed by Eq. (6) by swapping rows 2 and 3 with each other to give column 5 of ‘010’ as follows:
                    H        =                  (                                                    1                                            0                                            1                                            0                                            0                                            1                                                                    1                                            1                                            0                                            1                                            1                                            0                                                                    1                                            1                                            0                                            1                                            0                                            1                                              )                                    (        6        )            
Subsequently, the decoding apparatus carries out a basic deformation operation on the parity-check matrix H with column 1 taken as the important one. To put it concretely, the decoding apparatus transforms the parity check matrix H into a parity check matrix Hnew expressed by Eq. (7) by taking an exclusive logical sum of rows 1 and 3 and using the sum as a substitute for row 1 as well as taking an exclusive logical sum of rows 2 and 3 and using the sum as a substitute for row 2 to give column 1 of ‘001’ as follows:
                              H          new                =                  (                                                    0                                            1                                            1                                            1                                            0                                            0                                                                    0                                            0                                            0                                            0                                            1                                            1                                                                    1                                            1                                            0                                            1                                            0                                            1                                              )                                    (        7        )            
It is to be noted that if a specific column subjected to an attempt to carry out a diagonalization operation is linearly dependent on a column completing a diagonalization operation before the specific column, the decoding apparatus makes an attempt to carry out a diagonalization operation on a column of the next level of priority by keeping the specific column as it is. In this way, the decoding apparatus carries out a rank diagonalization operation on the parity check matrix H to produce the new parity check matrix Hnew.
Then, at the next step S4, the decoding apparatus carries out a belief propagation process by using the obtained new parity check matrix Hnew. The belief propagation process is carried out as a preparation to update the reliability level of each symbol at the following step S5.
FIG. 2 is a diagram showing Thanner graphs corresponding to the parity check matrix Hnew expressed by Eq. (7). A belief propagation process is implemented by letting a message go and come along edges of the Thanner graphs. In the diagram of FIG. 2, variable nodes are nodes corresponding to columns of a matrix. The variable nodes 11 to 16 shown in FIG. 2 correspond to the columns of the parity check matrix Hnew. On the other hand, check nodes are nodes corresponding to rows of a matrix. The check nodes 21 to 23 shown in FIG. 2 correspond to the rows of the parity check matrix Hnew.
In the following description, notations i and j each denote a natural number. Notation Ri,j denotes a message going from the ith variable node to the jth variable node. Notation Qi,j denotes a message going from the jth check node to the ith check node. Notation J (i) denotes a set of indexes for check nodes linked to the ith variable node. Notation I (j) denotes a set of indexes for variable nodes linked to the jth check node.
In this case, updating equations of messages Ri,j and Qi,j are expressed by Eqs. (8) and (9) respectively as follows.
                              R                      i            ,            j                          =                  2          ⁢                                          ⁢                                    tanh                              -                1                                      ⁡                          (                                                ∏                                      l                    ∈                                                                  I                        ⁡                                                  (                          j                          )                                                                    ⁢                      \                      ⁢                      i                                                                      ⁢                                  tanh                  ⁡                                      (                                                                  Q                                                  l                          ,                          j                                                                    /                      2                                        )                                                              )                                                          (        8        )                                          Q                      i            ,            j                          =                              r            i                    +                      θ            ⁢                                          ∑                                  l                  ∈                                                            J                      ⁡                                              (                        i                        )                                                              ⁢                    \                    ⁢                    j                                                              ⁢                              R                                  i                  ,                  l                                                                                        (        9        )            
A coefficient θ in Eq. (9) is a convergence coefficient known as a vertical step damping factor. The coefficient θ has a value in the range 0<θ≦1. The received symbol yj is set as the initial value of the message Qi,j.
Extrinsic information Λjx is updated in accordance with Eq. (10) as follows.
                                                              [                ⁢                              ⋀            i            x                    ⁢                      =                                          ∑                                  l                  ∈                                      J                    ⁡                                          (                      i                      )                                                                                  ⁢                                                R                                      i                    ,                    l                                                  ⁢                                                                                                                          ⁢                                                      (        10        )            
That is to say, at a step S5 of the flowchart shown in FIG. 1, the decoding apparatus computes an LLR (Log Likelihood Ratio) Λq of every coded symbol in accordance with Eq. (11) as follows:Λiq=ri+α1Λix  (11)
The LLR of a symbol is used as the reliability level of the symbol.
A coefficient α1 in Eq. (11) is a convergence coefficient known as an adaptive belief propagation damping factor. The coefficient α1 has a value in the range 0<α1≦1.
After computing the LLRs, the flow of the processing carried out by the decoding apparatus goes on to a step S6 at which the reliability-level order of the computed LLRs is recognized. To put it concretely, the decoding apparatus regards the magnitude of the absolute value of each computed LLR as the level of the reliability of the LLR in order to recognize the order of reliability levels. As will be described later, the LLRs are updated repeatedly till a predetermined condition is satisfied. The order of reliability levels is recognized to be used as an execution order for the diagonalization operation of the parity check matrix H in the next updating inner iteration loop from the step S3 to a step S8.
Then, at the next step S7, the decoding apparatus decodes the computed (updated) LLRs in order to obtain a decoded word. As a decoding technique, it is possible to adopt one of methods such as a hard decision decoding method, a limit distance decoding method and a K-V list decoding method. Subsequently, at the next step S8, the decoding apparatus produces a result of determination as to whether or not an inner-side repetitive decoding termination condition SC1 determined in advance is satisfied.
The operation of the step S5 to update LLRs on the basis of the belief propagation is carried out repeatedly till the repetitive decoding termination condition SC1 prepared in advance is satisfied. The decoding apparatus uses the reliability of each LLR updated at the step S5 on the basis of the belief propagation to re-update the LLRs at the step S5 in the next inner iteration loop. To put it concretely, the decoding apparatus takes the magnitude of the absolute value of each obtained LLR as a level of reliability at the step S6 and again carries out a diagonalization operation of the parity check matrix at the step S3 in an execution order starting with a column corresponding to a symbol having a lowest level of reliability as described before by referring to Eqs. (5) to (7). Then, the decoding apparatus re-updates the LLRs at the step S5 on the basis of a new belief propagation process carried out at the step S4. In addition, every time the decoding apparatus updates the LLRs, the decoding apparatus carries out a decoding process at the step S7 by using the updated LLRs. That is to say, the decoding apparatus carries out the decoding process repeatedly. This repetitive decoding processing is referred to as inner-side repetitive decoding processing. The decoding apparatus carries out the inner-side repetitive decoding processing repeatedly till the determination result produced at the step S8 indicates that the repetitive decoding termination condition SC1 prepared in advance is satisfied.
That is to say, if the determination result produced in the process carried out at the step S8 of the flowchart shown in FIG. 1 indicates that the inner-side repetitive decoding termination condition SC1 determined in advance is not satisfied, the flow of the processing carried out by the decoding apparatus goes back to the step S3 to repeat the processes of this step and the subsequent steps. If the determination result produced in the process carried out at the step S8 of the flowchart shown in FIG. 1 indicates that the inner-side repetitive decoding termination condition SC1 determined in advance is satisfied, on the other hand, the flow of the processing carried out by the decoding apparatus goes on to the step S9 cited above.
At the step S9, the decoding apparatus produces a result of determination as to whether or not an outer-side repetitive decoding termination condition SC2 determined in advance is satisfied. If the result of the determination indicates that the outer-side repetitive decoding termination condition SC2 determined in advance is not satisfied, the flow of the processing carried out by the decoding apparatus goes back to the step S2 to repeat the processes of this step and the subsequent steps.
That is to say, as an initial value of the priority order of the diagonalization operation carried out on columns of the parity check matrix H, the decoding apparatus prepares beforehand initial values according to a plurality of different methods each used for setting a priority order other than an order based on the aforementioned reliability levels of received symbols. Then, by adopting one of the prepared methods, the decoding apparatus carries out the inner-side repetitive decoding processes of the steps S3 to S8 concurrently or sequentially a plurality of times, that is, the decoding apparatus repeats the inner-side repetitive decoding processing. The repeated execution of the inner-side repetitive decoding processing of the steps S3 to S8 is referred to as the outer-side repetitive decoding processing, which also includes the step S2 for selecting the method to determine the basis of the priority order and the step S9. That is to say, the decoding apparatus carries out the outer-side repetitive decoding processing repeatedly till the determination result produced at the step S9 indicates that the outer-side repetitive decoding termination condition SC2 determined in advance is satisfied.
As an example, the following description explains typical repetitive decoding termination conditions SC for a case in which the linear code serving as an object of processing is the Reed-Solomon code.
Let us assume for example that notation N denotes a predetermined maximum repetition count representing the maximum number of repetitions and the hard decision result of Λq is d (=d1, d2, . . . , d6). The hard decision result di is expressed by Eq. (12) as follows.di=1 for Λiq>0 ordi=0 for Λiq≦0  (12)
In this case, the decoding apparatus may typically adopt a repetitive decoding termination condition SC, which requires that the product of the parity check matrix H and the hard decision result d shall be zero (that is, H×d=0), the repetition count t shall be equal to or greater than the predetermined maximum repetition count N (that is, t≧N) or both the conditions of (H×d=0) and (t≧N) shall be satisfied. In this case, the repetitive decoding termination condition SC can be used as the inner-side repetitive decoding termination condition SC1 or the outer-side repetitive decoding termination condition SC2.
As an alternative, the decoding apparatus may also adopt a repetitive decoding termination condition SC, which requires that a limit distance decoding process shall have been successful, the repetition count t shall be equal to or greater than the predetermined maximum repetition count N (that is, t≧N) or both the conditions of a successful limit distance decoding process and (t≧N) shall be satisfied. Also in this case, the repetitive decoding termination condition SC can be used as the inner-side repetitive decoding termination condition SC1 or the outer-side repetitive decoding termination condition SC2.
As another alternative, the decoding apparatus may also adopt a repetitive decoding termination condition SC, which requires that at least the k-v list decoding process has been successful or the repetition count t shall be equal to or greater than the predetermined maximum repetition count N (that is, t≧N). Also in this case, the repetitive decoding termination condition SC can be used as the inner-side repetitive decoding termination condition SC1 or the outer-side repetitive decoding termination condition SC2.
If the determination result produced in a process carried out at the step S9 after the outer-side repetitive decoding processing described above has been completed indicates that the outer-side repetitive decoding termination condition SC2 is satisfied, the decoding apparatus ends the execution of the decoding processing.